import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2022-10-28
 * Time: 10:41
 */

public class MyPriorityQueue {
    /**
     * 堆的底层是一个完全二叉树
     * 存储为数组中，且完全二叉树一般不会浪费空间
     * 非完全二叉树不适合顺序存储
     */

    public int[] elem; // 底层为数组
    public int usedSize;  // 数组中的有效个数
    public final int DEFAULT = 10;

    public MyPriorityQueue() {
        this.elem = new int[DEFAULT];
    }

    public boolean isFull() {
        return usedSize - this.elem.length >= 0;
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }

    // 自动添加元素
    public void addElem(int[] array) {

        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
            if (isFull()) {
                this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
            }
        }
    }

    /**
     * 时间复杂度： O（logN） -- 从根调整到叶子节点--树得高度
     * 大根堆 - 根节点比左右子节点大
     */
    public void createMaxheap() {
        // 传一个调整一个
        //    已知孩子推导父亲（从最后一个节点开始）  0位置需要调整
        for (int parent = (usedSize - 2) / 2; parent >= 0; parent--) {
            shiftDown(parent, usedSize);
        }
    }

    /**
     * 向下调整某个节点
     *
     * @param parent 孩子节点得父亲节点
     * @param len    每个孩子节点结束位置   < len
     */
    public void shiftDown(int parent, int len) {
        int child = 2 * parent + 1;
        // 1. 没有左子树时，孩子节点越界 -- 必须保证有左孩子
        while (child < len) {
            // child+1 < lne 保证一定有右孩子 且不越界
            if ((child + 1) < len && elem[child] > elem[child + 1]) {
                child++;
            }
            // 此时child 下标为左右孩子节点得最大值下标
            if (elem[child] < elem[parent]) {
                //交换
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                // 向下继续调整
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }


    /**
     * 大根堆情况下, 插入新元素 O(logN) - 从底下插入一个比 root 大的数
     */
    public void offer(int val) {
        if (isFull()) ;

        // 往数组最后一个位置插入元素
        elem[usedSize++] = val;

        // 插入后可能影响原来的堆排序, 进行调整
        shiftUp(usedSize - 1);
    }

    /**
     * 已经是大根堆的情况下, 进行插入元素的向上调整
     */
    private void shiftUp(int child) {
        // 获取插入新元素的父节点
        int parent = (child - 1) / 2;

        // parent >= 0
        while (parent >= 0) {
            // 新插入的元素比父节点大, 可以不用考虑父节点的另外一个字节点
            // 已经是大根堆了进行调整, 父节点就是这个子堆最大的值
            if (elem[child] > elem[parent]) {
                // 交换新节点和父节点值
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;

                // 当前这个父节点的子堆调整好了, 有可能影响父节点的祖父节点, 因此需要向上继续调整
                child = parent;
                parent = (child - 1) / 2;
            } else {
                // 新插入的节点没有其父节点大, 不再需要更新
                break;
            }
        }
    }

    /**
     * 弹出队首元素
     */
    public int pop() {
        if (isEmpty()) {
            throw new EmptyException("当前优先级队列为空, 无法弹出队首元素");
        }

        // 将队首元素和队尾元素调换
        int tmp = elem[0];
        elem[0] = elem[usedSize - 1];
        elem[usedSize - 1] = tmp;

        // 删掉调换到队尾的原本为队首的元素
        usedSize--;

        // 从 0 下标的堆开始向下调整使其重新成为大根堆
        shiftDown(0, usedSize);

        return tmp;
    }

    /**
     * 小根堆 - 根节点比左右子节点小
     */
    public void minheap() {

    }

    public void disPlay() {
        for (int i = 0; i < usedSize; i++) {
            System.out.println(elem[i]);
        }
    }

}
